|
In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002.〔(M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. )〕 Like some other fountain codes, LT codes depend on sparse bipartite graphs to trade reception overhead for encoding and decoding speed. The distinguishing characteristic of LT codes is in employing a particularly simple algorithm based on the exclusive or operation () to encode and decode the message.〔The ''exclusive or'' (XOR) operation, symbolized by ⊕, has the very useful property that ''A'' ⊕ ''A'' = 0, where ''A'' is an arbitrary string of bits.〕 LT codes are ''rateless'' because the encoding algorithm can in principle produce an infinite number of message packets (i.e., the percentage of packets that must be received to decode the message can be arbitrarily small). They are ''erasure correcting codes'' because they can be used to transmit digital data reliably on an erasure channel. The next generation beyond LT codes are raptor codes (see for example IETF RFC 5053 or IETF RFC 6330), which have linear time encoding and decoding. Raptor codes use two encoding stages for encoding, where the second stage is an LT encoding. ==Why use an LT code?== The traditional scheme for transferring data across an erasure channel depends on continuous two-way communication. *The sender encodes and sends a packet of information. *The receiver attempts to decode the received packet. If it can be decoded, the receiver sends an acknowledgment back to the transmitter. Otherwise, the receiver asks the transmitter to send the packet again. *This two-way process continues until all the packets in the message have been transferred successfully. Certain networks, such as ones used for cellular wireless broadcasting, do not have a feedback channel. Applications on these networks still require reliability. Fountain codes in general, and LT codes in particular, get around this problem by adopting an essentially one-way communication protocol. *The sender encodes and sends packet after packet of information. *The receiver evaluates each packet as it is received. If there is an error, the erroneous packet is discarded. Otherwise the packet is saved as a piece of the message. *Eventually the receiver has enough valid packets to reconstruct the entire message. When the entire message has been received successfully the receiver signals that transmission is complete. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Luby transform code」の詳細全文を読む スポンサード リンク
|